#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "algorithm.h"
#include <math.h>

/**
 * @brief  算法接口
 * @param  input            输入参数
 * @param  output           输出参数
 * @return int32_t          返回成功或者失败，RETURN_OK 或 RETURN_ERROR
 */
#define POPULATION_SIZE 50
#define GENERATION_COUNT 100
#define CROSSOVER_RATE 0.8
#define MUTATION_RATE 0.02
#define INITIAL_TEMPERATURE 1000.0
#define COOLING_RATE 0.95
double expe(double x)
{
    int32_t T=8;
    x = 1.0 + x/256;
    while(T--) x *= x;
    return x;
}
void initialize_population(Individual *population, int population_size, int num_cities, const InputParam *input) {
    srand(time(NULL));
    for (int i = 0; i < population_size; i++) {
        population[i].path = (OutputParam *)malloc(sizeof(OutputParam));
        population[i].path->len = num_cities;
        population[i].path->sequence = (uint32_t *)malloc(num_cities * sizeof(uint32_t));
        for (int j = 0; j < num_cities; j++) {
            population[i].path->sequence[j] = j+1;
        }
        for (int j = 0; j < num_cities; j++) {
            int r = rand() % num_cities;
            uint32_t temp = population[i].path->sequence[j];
            population[i].path->sequence[j] = population[i].path->sequence[r];
            population[i].path->sequence[r] = temp;
        }
        AccessTime accessTime = {0};// 访问时间
        TotalAccessTime(input, population[i].path, &accessTime);
        population[i].cost = accessTime.addressDuration;

    }
}

// 交叉操作
void crossover(OutputParam *parent1, OutputParam *parent2, OutputParam *child, int num_cities) {
    srand(time(NULL));
    int start = rand() % num_cities;
    int end = rand() % num_cities;

    if (start > end) {
        int temp = start;
        start = end;
        end = temp;
    }

    int *visited = (int *)calloc(num_cities+1, sizeof(int));// 申请num_cities个int大小的内存空间，并初始化为0
    for (int i = start; i <= end; i++) {
        child->sequence[i] = parent1->sequence[i];
        visited[parent1->sequence[i]] = 1;
    }
    int current = 0;
    for (int i = 0; i < num_cities; i++) {
        if (!visited[parent2->sequence[i]]) {
            while (current >= start && current <= end) {
                current++;
            }
            child->sequence[current++] = parent2->sequence[i];// 从start到end的位置已经被parent1占据，所以从start到end的位置不用再赋值
        }
    }

    free(visited);
}

// 变异操作
void mutation(OutputParam *path, int num_cities) {
    srand(time(NULL));
    int index1 = rand() % num_cities;
    int index2 = rand() % num_cities;
    uint32_t temp = path->sequence[index1];
    path->sequence[index1] = path->sequence[index2];
    path->sequence[index2] = temp;
}

// 模拟退火操作
void simulated_annealing(const InputParam *input, Individual *individual, int num_cities) {
    double temperature = INITIAL_TEMPERATURE;
    double cooling_rate = COOLING_RATE;
    uint32_t *new_path = (uint32_t *)malloc(num_cities * sizeof(uint32_t));
    while (temperature > 0.1) {
        // 复制当前路径到新路径
        for (int i = 0; i < num_cities; i++) {
            new_path[i] = individual->path->sequence[i];
        }

        // 随机选择两个城市进行交换
        int index1 = rand() % num_cities;
        int index2 = rand() % num_cities;
        uint32_t temp = new_path[index1];
        new_path[index1] = new_path[index2];
        new_path[index2] = temp;

        // 计算新路径的总距离
        int32_t current_distance = individual->cost;
        AccessTime new_accessTime = {0};
        OutputParam new_output;
        new_output.len = num_cities;
        new_output.sequence = new_path;
        TotalAccessTime(input, &new_output, &new_accessTime);
        int32_t new_distance = new_accessTime.addressDuration;

        // 如果新路径更短，或者以一定概率接受更长的路径
        if (new_distance < current_distance) {
            for (int i = 0; i < num_cities; i++) {
                individual->path->sequence[i] = new_path[i];
            }
            individual->cost = new_distance;
        } else {// 以一定概率接受更长的路径
            double probability = expe(((double)(current_distance - new_distance)) / temperature);// 以一定概率接受更长的路径
            if ((double)rand() / RAND_MAX < probability) {
                for (int i = 0; i < num_cities; i++) {
                    individual->path->sequence[i] = new_path[i];
                }
                individual->cost = new_distance;
            }
        }

        // 降低温度
        temperature *= cooling_rate;
    }
    free(new_path);
}

void genetic_simulated_annealing(const InputParam *input, int num_cities, OutputParam *output) {
    srand(time(NULL));
    double temperature = INITIAL_TEMPERATURE;
    Individual *population = (Individual *)malloc(POPULATION_SIZE * sizeof(Individual));
    initialize_population(population, POPULATION_SIZE, num_cities, input);
    for (int gen = 0; gen < GENERATION_COUNT; gen++) {
        Individual *new_population = (Individual *)malloc(POPULATION_SIZE * sizeof(Individual));
        for (int i = 0; i < POPULATION_SIZE; i++) {
            for (int j = i + 1; j < POPULATION_SIZE; j++) {
                if (population[i].cost > population[j].cost) {
                    Individual temp = population[i];
                    population[i] = population[j];
                    population[j] = temp;
                }
            }
        }
        int elite_count = (int)(POPULATION_SIZE * 0.2);
        for (int i = 0; i < elite_count; i++) {
            new_population[i].path = (OutputParam *)malloc(sizeof(OutputParam));
            new_population[i].path->len = num_cities;
            new_population[i].path->sequence = (uint32_t *)malloc(num_cities * sizeof(uint32_t));
            for (int j = 0; j < num_cities; j++) {
                new_population[i].path->sequence[j] = population[i].path->sequence[j];
            }
            new_population[i].cost = population[i].cost;
        }// 保留前20%的精英个体
        for (int i = elite_count; i < POPULATION_SIZE; i++) {
            OutputParam *parent1 = population[rand() % elite_count].path;
            OutputParam *parent2 = population[rand() % POPULATION_SIZE].path;
            new_population[i].path = (OutputParam *)malloc(sizeof(OutputParam));
            new_population[i].path->len = num_cities;
            new_population[i].path->sequence = (uint32_t *)malloc(num_cities * sizeof(uint32_t));
            crossover(parent1, parent2, new_population[i].path, num_cities);
            AccessTime accessTime = {0};// 访问时间
            TotalAccessTime(input, new_population[i].path, &accessTime);
            new_population[i].cost = accessTime.addressDuration;
        }
        for (int i = 0; i < POPULATION_SIZE; i++) {
            if (rand() % 100 < MUTATION_RATE*100) {// 以MUTATION_RATE的概率进行变异
                mutation(new_population[i].path, num_cities);
                AccessTime accessTime = {0};// 访问时间
                TotalAccessTime(input, new_population[i].path, &accessTime);
                new_population[i].cost = accessTime.addressDuration;
            }
        }
        for (int i = 0; i < POPULATION_SIZE; i++) {
            simulated_annealing(input, &new_population[i], num_cities);
        }
        for (int i = 0; i < POPULATION_SIZE; i++) {
            free(population[i].path->sequence);
            free(population[i].path);
        }
        for (int i = 0; i < POPULATION_SIZE; i++) {
            population[i] = new_population[i];
        }
        free(new_population);
    }
    Individual best_individual = population[0];
    for (int i = 1; i < POPULATION_SIZE; i++) {
        if (population[i].cost < best_individual.cost) {
            best_individual = population[i];
        }
    }
    for (int i = 0; i < num_cities; i++) {
        output->sequence[i] = best_individual.path->sequence[i];
    }
    for (int i = 0; i < POPULATION_SIZE; i++) {
        free(population[i].path->sequence);
        free(population[i].path);
    }
    free(population);
}
int32_t IOScheduleAlgorithm(const InputParam *input, OutputParam *output)
{
    srand(time(NULL));
    output->len = input->ioVec.len;
    genetic_simulated_annealing(input, output->len, output);
    return RETURN_OK;
}
/**
 * @brief  算法运行的主入口
 * @param  input            输入参数
 * @param  output           输出参数
 * @return uint32_t          返回成功或者失败，RETURN_OK 或 RETURN_ERROR
 */
int32_t AlgorithmRun(const InputParam *input, OutputParam *output)
{
    int32_t ret;

    ret = IOScheduleAlgorithm(input, output);

    return RETURN_OK;
}